A very large data store system may be implemented as a distributed data store such that data is stored on a plurality of separate memory devices, for example separate disk drives. Such disk drives are sometimes referred to as back end data storage. Client applications may read and write the data in the distributed data stores, and the distributed data store may map these access requests to the appropriate memory devices. To avoid having to buy and deploy additional storage resources as data grows, sometimes data may be aged out and discarded to make room for new inflowing data. For example, the oldest data may be overwritten by new data. Alternatively, old data may first be deleted or marked as available for writing, and then new data may be written in the place where the old data had previously been written.